package sort;

/**
 * @author qiss
 * @create 2018-04-19 18:30
 **/
public class MergeSort {

    private static void merge(int[] list,int low,int mid,int high){
        int[] temp = new int[high-low+1];
        int i = low;
        int j = mid+1;
        int k = 0;
        while(i<=mid && j<=high){
            if(list[i] <= list[j]){
                temp[k++] = list[i++];
            }else{
                temp[k++] = list[j++];
            }
        }
        while(i <= mid){
            temp[k++] = list[i++];
        }
        while(j <= high){
            temp[k++] = list[j++];
        }
        for (k = 0;k< temp.length;k++){
            list[low++] = temp[k];
        }

    }


    private static void mergeSort(int[] list,int low,int high){
        int mid = (low+high)/2;
        if (low < high){
            mergeSort(list,low,mid);
            mergeSort(list,mid+1,high);
            merge(list,low,mid,high);
        }
    }


    public static void main(String[] args) {
        int[] list = {49,38,65,97,76,13,27};
        mergeSort(list,0,list.length-1);
        for (int i = 0; i < list.length; i++) {
            System.out.println(list[i]);
         }
    }
}
